import common.TreeNode;

/**
 * 114. Flatten Binary Tree to Linked List 二叉树展开为链表
 * https://leetcode-cn.com/problems/flatten-binary
 */
class FlattenBinaryTreeToLinkedList {
    private TreeNode head;

    /**
     *     方法：flatten 将二叉树展开为链表
     *
     *     使用后序遍历的方式（右-左-根）将二叉树展开为链表。
     *     通过维护一个全局的head指针，将当前节点的右指针指向之前处理的节点，
     *     并将左指针置为空，从而实现二叉树到链表的转换。
     *
     *     Args:
     *         root: Optional[TreeNode] - 二叉树的根节点
     *
     *     Returns:
     *         None - 直接在原树上修改
     *
     *     Time: O(n) - 其中n是二叉树的节点数，每个节点只被访问一次
     *
     *     Space: O(h) - 其中h是二叉树的高度，递归调用栈的空间
     */
    public void flatten(TreeNode root) {
        if (root == null){
            return;
        }
        flatten(root.right);
        flatten(root.left);
        root.left = null;
        root.right = head; //root.next = head
        head = root;
    }

    /**
     *     方法：flatten1 将二叉树展开为链表（迭代方式）
     *
     *     通过迭代方式将二叉树展开为链表。对于每个节点，如果它有左子树，
     *     则找到左子树的最右节点，将当前节点的右子树接到这个最右节点的右指针上，
     *     然后将左子树移到右子树的位置，并将左指针置为空。
     *
     *     Args:
     *         root: Optional[TreeNode] - 二叉树的根节点
     *
     *     Returns:
     *         None - 直接在原树上修改
     *
     *     Time: O(n) - 其中n是二叉树的节点数，每个节点最多被访问两次
     *
     *     Space: O(1) - 只使用常数额外空间
     */
    public void flatten1(TreeNode root) {
        TreeNode cur = root;
        while(cur != null){
            if(cur.left != null){
                TreeNode next = cur.left;
                TreeNode pre = next;
                while (pre.right != null){
                    pre = pre.right;
                }
                pre.right = cur.right;
                cur.left = null;
                cur.right = next;
            }
            cur = cur.right;
        }
    }
}